/*
 * @lc app=leetcode.cn id=40 lang=javascript
 *
 * [40] 组合总和 II
 */

// @lc code=start
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  let length = candidates.length,
    targetArr = [],
    resultArr = []
  candidates = candidates.sort((a, b) => a - b)

  const backtrack = (targetArr, target, start) => {
    if (target == 0) {
      resultArr.push(targetArr)
      return
    }
    for (let i = start; i < length; i++) {
      if (i > start && candidates[i] == candidates[i - 1]) continue
      if (target - candidates[i] >= 0) {
        // i位置的选择的，所以从i+1开始选
        backtrack([...targetArr, candidates[i]], target - candidates[i], i + 1)
      }
    }
  }

  backtrack(targetArr, target, 0)
  return resultArr
}
// @lc code=end
